struct Edge {
  int u,v,cost;
};
Edge e[1001*1001];
int pre[1001],id[1001],visit[1001],in[1001];
int zhuliu(int root,int n,int m,Edge e[]) {
  int res = 0,u,v;
  while (true) {
    for (int i = 0; i < n; i++)
      in[i] = inf;
    for (int i = 0; i < m; i++)
      if (e[i].u != e[i].v && e[i].cost < in[e[i].v]) {
        pre[e[i].v] = e[i].u;
        in[e[i].v] = e[i].cost;
      }
    for (int i = 0; i < n; i++)
      if (i != root)
        if (in[i] == inf)   return -1;
    int tn = 0;
    memset(id,-1,sizeof(id));
    memset(visit,-1,sizeof(visit));
    in[root] = 0;
    for (int i = 0; i < n; i++) {
      res += in[i];
      v = i;
      while (visit[v] != i && id[v] == -1 && v != root) {
        visit[v] = i;
        v = pre[v];
      }
      if(v != root && id[v] == -1) {
        for(int u = pre[v] ; u != v ; u = pre[u])
          id[u] = tn;
        id[v] = tn++;
      }
    }
    if(tn == 0)	break;
    for (int i = 0; i < n; i++)
      if (id[i] == -1)
        id[i] = tn++;
    for (int i = 0; i < m;) {
      int v = e[i].v;
      e[i].u = id[e[i].u];
      e[i].v = id[e[i].v];
      if (e[i].u != e[i].v)
        e[i++].cost -= in[v];
      else
        swap(e[i],e[--m]);
    }
    n = tn;
    root = id[root];
  }
  return res;
}

